Corelab Seminar
2019-2020
Manolis Vlatakis
(Hidden) Zero-Sum Games: The Final (Non-Convex Non-Concave) Frontier
A story by Poincaré, Bendixson, Hamilton and von Neumann
Abstract.
A fundamental question of game theory is how will agents participating in a game behave over time. Will their dynamics equilibrate? If not, canwe make any other predictions about their long term behavior?
Recently this problem has attracted renewed interest motivated by the advent of Generative Adversarial Networks (GANs) and their numerous applications. This AI architecture is effectively a zero-sum game between two NNs (Generator & Discriminator) that are trying to outcompete each other, critically they do not belong in the standard class of convex-concave games where the minmax theorem applies.
In this work, motivated by the indirect nature of the competition in GANS, where players control the parameters of a neural network while the actual competition happens between the distributions that the generator and discriminator capture, we study a wide class of non-convex non-concave min-max games that generalizes over standard bilinear zero-sum games. In this class, players control the inputs of a smooth function whose output is being applied to a bilinear zero-sum game. We establish theoretically, that depending on the specific instance of the problem gradient-descent-ascent dynamics can exhibit a variety of behaviors antithetical to convergence to the game theoretically meaningful min-max solution. Specifically, different forms of recurrent behavior (including periodicity and Poincaré recurrence) are possible as well as convergence to spurious (non-min-max) equilibria for a positive measure of initial conditions. At the technical level, our analysis combines tools from optimization theory, game theory and dynamical systems.